import java.util.*;

public class SlidingWindow {
    //长度最小的数组
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = 0;
        int len = Integer.MAX_VALUE;
        int sum = 0;
        for (; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {
                len = Math.min(len, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        return len == Integer.MAX_VALUE ? 0 : len;
    }
    //数组方法

    public int lengthOfLongestSubstring(String ss) {
          char[] s=ss.toCharArray();
          int[] hash=new int[128];
          int left=0,right=0;
          int len=0;
          while (right<s.length){
              hash[s[right]]++;
              while (hash[s[right]]>1){
                  hash[s[left]]--;
                  left++;
              }
              len=Math.max(len,right-left+1);
              right++;
          }
          return len;
    }
    //hash表
    public int lengthOfLongestSubstring1(String ss) {
        char[] s=ss.toCharArray();
        Map<Character,Integer> hash=new HashMap<>();
        int left=0,right=0;
        int len=0;
        while (right<s.length){

            while (hash.containsKey(s[right])){
                hash.remove(s[left]);
                left++;
            }hash.put(s[right],right);
            len=Math.max(len,right-left+1);
            right++;
        }
        return len;
    }
//水果成篮你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
//
//你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
//
//你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
//你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
//一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
//给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
//
//
//
//示例 1：
//
//输入：fruits = [1,2,1]
//输出：3
//解释：可以采摘全部 3 棵树。
//示例 2：
//
//输入：fruits = [0,1,2,2]
//输出：3
//解释：可以采摘 [1,2,2] 这三棵树。
//如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。
//示例 3：
//
//输入：fruits = [1,2,3,2,2]
//输出：4
//解释：可以采摘 [2,3,2,2] 这四棵树。
//如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。
//示例 4：
//
//输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
//输出：5
//解释：可以采摘 [1,2,1,1,2] 这五棵树。
//
//
//提示：
//
//1 <= fruits.length <= 105
//0 <= fruits[i] < fruits.length
public int totalFruit(int[] fruits) {
    Map<Integer,Integer> hash=new HashMap<Integer,Integer>();
    int ret=0;
    for(int right=0,left=0;right<fruits.length;right++){
        int in=fruits[right];
        hash.put(in,hash.getOrDefault(in,0)+1);
        while(hash.size()>2){
            int out=fruits[left];
            hash.put(out,hash.get(out)-1);
            if(hash.get(out)==0){
                hash.remove(out);

            }
            left++;
        }
        ret=Math.max(ret,right-left+1);}
    return ret;
}
//字母异位
    public List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> list=new ArrayList<>();
        Map<Character,Integer> hash2=new HashMap<>();
        char[] p=pp.toCharArray();
        for(char c:p){
            hash2.put(c,hash2.getOrDefault(c,0)+1);
        }
        Map<Character,Integer> hash1=new HashMap<>();
        char[] s=ss.toCharArray();
        for(int left=0,right=0;right<s.length;right++){
            char in=s[right];
            hash1.put(in,hash1.getOrDefault(in,0)+1);
            if(right-left+1==p.length){
                if(hash1.equals(hash2)){
                    list.add(left);
                }
                char out=s[left];
                if(hash1.get(out)==1){
                    hash1.remove(out);
                }else{
                    hash1.put(out,hash1.get(out)-1);
                }
                left++;
            }
        }
        return list;
    }
    //数组hash表
    public List<Integer> findAnagrams1(String ss, String pp) {
        List<Integer> list=new ArrayList<>();
        int[] hash1=new int[26];
        int[] hash2=new int[26];
        char[] p=pp.toCharArray();
        char[] s=ss.toCharArray();
        for(char t:p){
            hash2[t-'a']++;
        }
        for(int left=0,right=0;right<s.length;right++){
            hash1[s[right]-'a']++;
            if(right-left+1==p.length){
                if(Arrays.equals(hash1,hash2)){
                    list.add(left);
                }

                hash1[s[left]-'a']--;
                left++;
            }

        }
        return list;
    }
    //count计数

    //
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> List=new ArrayList<>();
        int len=words[0].length();
        Map<String,Integer> hash2=new HashMap<>();
        for(String n:words){
            hash2.put(n,hash2.getOrDefault(n,0)+1);
        }
        for(int i=0;i<len;i++){
            Map<String,Integer> hash1=new HashMap<>();

            for(int right=i, left=i,count=0;right+len<=s.length();right+=len){

                String in=s.substring(right,right+len);
                hash1.put(in,hash1.getOrDefault(in,0)+1);
                if(hash1.get(in)<=hash2.getOrDefault(in,0)){
                    //与数组那里不一样，这里由于没有key值就没有数据，所以需要用这个方法
                    count++;
                }
                if(right-left+1>words.length*len){
                    String out=s.substring(left,left+len);
                    if(hash1.get(out)<=hash2.getOrDefault(out,0)){
                        count--;
                    }
                    hash1.put(out,hash1.get(out)-1);
                    left+=len;
                }
                if(count==words.length){
                    List.add(left);
                }
            }

        }
        return List;
    }
    }
